package com.atguigu.algorithm;

import java.util.HashMap;

public class RandomPool<K>{
    public HashMap<K,Integer> map1;
    public HashMap<Integer,K> map2;
    public int size;
    public RandomPool(){
        map1=new HashMap<>();
        map2=new HashMap<>();
        size=0;
    }
    public void insert(K key){
        if(!map1.containsKey(key)){
            map1.put(key,size);
            map2.put(size++,key);
        }
    }
    public void delete(K key){
        if(map1.containsKey(key)){
            K lastK=map2.get(--size); //先得到最后一个值的key
            int deleteIndex=map1.get(key); //要删除值的index
            map2.replace(deleteIndex,lastK); //将map2中的位置上替换
            map1.remove(key);
            map1.put(lastK,deleteIndex);
        }
    }
    public K getRandom(){
        if(size==0){
            return null;
        }
        int randomIndex=(int)(Math.random()*this.size);
        return map2.get(randomIndex);
    }
}
